home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 2 / AACD 2.iso / AACD / Magazine / GraphicsCards / StormMesa / src / clip.c < prev    next >
C/C++ Source or Header  |  1999-02-04  |  31KB  |  1,038 lines
  1. /* $Id: clip.c,v 3.5 1998/06/21 02:00:55 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  3.0
  6.  * Copyright (C) 1995-1998  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: clip.c,v $
  26.  * Revision 3.5  1998/06/21 02:00:55  brianp
  27.  * cleaned up clip interpolation function code
  28.  *
  29.  * Revision 3.4  1998/03/27 03:30:36  brianp
  30.  * fixed G++ warnings
  31.  *
  32.  * Revision 3.3  1998/02/20 04:50:09  brianp
  33.  * implemented GL_SGIS_multitexture
  34.  *
  35.  * Revision 3.2  1998/02/08 20:16:50  brianp
  36.  * removed unneeded headers
  37.  *
  38.  * Revision 3.1  1998/02/03 23:46:40  brianp
  39.  * added 'space' parameter to clip interpolation functions
  40.  *
  41.  * Revision 3.0  1998/01/31 20:48:09  brianp
  42.  * initial rev
  43.  *
  44.  */
  45.  
  46.  
  47. #ifdef PC_HEADER
  48. #include "all.h"
  49. #else
  50. #include <string.h>
  51. #include "clip.h"
  52. #include "context.h"
  53. #include "macros.h"
  54. #include "matrix.h"
  55. #include "types.h"
  56. #include "vb.h"
  57. #include "xform.h"
  58. #endif
  59.  
  60.  
  61.  
  62.  
  63. /* Linear interpolation between A and B: */
  64. #define LINTERP( T, A, B )   ( (A) + (T) * ( (B) - (A) ) )
  65.  
  66.  
  67. /* Clipping coordinate spaces */
  68. #define EYE_SPACE 1
  69. #define CLIP_SPACE 2
  70.  
  71.  
  72.  
  73.  
  74. /*
  75.  * This function is used to interpolate colors, indexes, and texture
  76.  * coordinates when clipping has to be done.  In general, we compute
  77.  *     aux[dst] = aux[in] + t * (aux[out] - aux[in])
  78.  * where aux is the quantity to be interpolated.
  79.  * Input:  dst - index of array position to store interpolated value
  80.  *         t - a value in [0,1]
  81.  *         in - index of array position corresponding to 'inside' vertex
  82.  *         out - index of array position corresponding to 'outside' vertex
  83.  */
  84. void gl_clip_interp_all( GLcontext *ctx, GLuint space,
  85.                          GLuint dst, GLfloat t, GLuint in, GLuint out )
  86. {
  87.    struct vertex_buffer *VB = ctx->VB;
  88.  
  89.    if (ctx->ClipMask & CLIP_FCOLOR_BIT) {
  90.       VB->Fcolor[dst][0] = (GLint) LINTERP( t, VB->Fcolor[in][0], VB->Fcolor[out][0] );
  91.       VB->Fcolor[dst][1] = (GLint) LINTERP( t, VB->Fcolor[in][1], VB->Fcolor[out][1] );
  92.       VB->Fcolor[dst][2] = (GLint) LINTERP( t, VB->Fcolor[in][2], VB->Fcolor[out][2] );
  93.       VB->Fcolor[dst][3] = (GLint) LINTERP( t, VB->Fcolor[in][3], VB->Fcolor[out][3] );
  94.    }
  95.    else if (ctx->ClipMask & CLIP_FINDEX_BIT) {
  96.       VB->Findex[dst] = (GLuint) (GLint) LINTERP( t, (GLfloat) VB->Findex[in],
  97.                                                  (GLfloat) VB->Findex[out] );
  98.    }
  99.  
  100.    if (ctx->ClipMask & CLIP_BCOLOR_BIT) {
  101.       VB->Bcolor[dst][0] = (GLubyte) LINTERP( t, VB->Bcolor[in][0], VB->Bcolor[out][0] );
  102.       VB->Bcolor[dst][1] = (GLubyte) LINTERP( t, VB->Bcolor[in][1], VB->Bcolor[out][1] );
  103.       VB->Bcolor[dst][2] = (GLubyte) LINTERP( t, VB->Bcolor[in][2], VB->Bcolor[out][2] );
  104.       VB->Bcolor[dst][3] = (GLubyte) LINTERP( t, VB->Bcolor[in][3], VB->Bcolor[out][3] );
  105.    }
  106.    else if (ctx->ClipMask & CLIP_BINDEX_BIT) {
  107.       VB->Bindex[dst] = (GLuint) (GLint) LINTERP( t, (GLfloat) VB->Bindex[in],
  108.                                                  (GLfloat) VB->Bindex[out] );
  109.    }
  110.  
  111.    if (ctx->ClipMask & CLIP_TEXTURE_BIT) {
  112.       GLuint i;
  113.       if (space==CLIP_SPACE) {
  114.      /* also interpolate eye Z component */
  115.      VB->Eye[dst][2] = LINTERP( t, VB->Eye[in][2], VB->Eye[out][2] );
  116.       }
  117.       for (i=0;i<MAX_TEX_SETS;i++) {
  118.          VB->MultiTexCoord[i][dst][0] = LINTERP(t,VB->MultiTexCoord[i][in][0],VB->MultiTexCoord[i][out][0]);
  119.          VB->MultiTexCoord[i][dst][1] = LINTERP(t,VB->MultiTexCoord[i][in][1],VB->MultiTexCoord[i][out][1]);
  120.          VB->MultiTexCoord[i][dst][2] = LINTERP(t,VB->MultiTexCoord[i][in][2],VB->MultiTexCoord[i][out][2]);
  121.          VB->MultiTexCoord[i][dst][3] = LINTERP(t,VB->MultiTexCoord[i][in][3],VB->MultiTexCoord[i][out][3]);
  122.       }
  123.    }
  124.  
  125. }
  126.  
  127.  
  128. /*
  129.  * Specialized version gl_clip_interp_all:  just do color and texcoords.
  130.  */
  131. void gl_clip_interp_color_tex( GLcontext *ctx, GLuint space,
  132.                                GLuint dst, GLfloat t, GLuint in, GLuint out )
  133. {
  134.    struct vertex_buffer *VB = ctx->VB;
  135.    VB->Fcolor[dst][0] = (GLint) LINTERP( t, VB->Fcolor[in][0], VB->Fcolor[out][0] );
  136.    VB->Fcolor[dst][1] = (GLint) LINTERP( t, VB->Fcolor[in][1], VB->Fcolor[out][1] );
  137.    VB->Fcolor[dst][2] = (GLint) LINTERP( t, VB->Fcolor[in][2], VB->Fcolor[out][2] );
  138.    VB->Fcolor[dst][3] = (GLint) LINTERP( t, VB->Fcolor[in][3], VB->Fcolor[out][3] );
  139.  
  140.    VB->Eye[dst][2] = LINTERP( t, VB->Eye[in][2], VB->Eye[out][2] );
  141.    VB->TexCoord[dst][0] = LINTERP(t,VB->TexCoord[in][0],VB->TexCoord[out][0]);
  142.    VB->TexCoord[dst][1] = LINTERP(t,VB->TexCoord[in][1],VB->TexCoord[out][1]);
  143.    if (VB->TexCoordSize != 2) {
  144.       VB->TexCoord[dst][2] = LINTERP(t,VB->TexCoord[in][2],VB->TexCoord[out][2]);
  145.       VB->TexCoord[dst][3] = LINTERP(t,VB->TexCoord[in][3],VB->TexCoord[out][3]);
  146.    }
  147.    (void) space;
  148. }
  149.  
  150.  
  151. /*
  152.  * Specialized version gl_clip_interp_all:  just do texcoords.
  153.  */
  154. void gl_clip_interp_tex( GLcontext *ctx, GLuint space,
  155.                          GLuint dst, GLfloat t, GLuint in, GLuint out )
  156. {
  157.    struct vertex_buffer *VB = ctx->VB;
  158.    VB->Eye[dst][2] = LINTERP( t, VB->Eye[in][2], VB->Eye[out][2] );
  159.    VB->TexCoord[dst][0] = LINTERP(t,VB->TexCoord[in][0],VB->TexCoord[out][0]);
  160.    VB->TexCoord[dst][1] = LINTERP(t,VB->TexCoord[in][1],VB->TexCoord[out][1]);
  161.    if (VB->TexCoordSize != 2) {
  162.       VB->TexCoord[dst][2] = LINTERP(t,VB->TexCoord[in][2],VB->TexCoord[out][2]);
  163.       VB->TexCoord[dst][3] = LINTERP(t,VB->TexCoord[in][3],VB->TexCoord[out][3]);
  164.    }
  165.    (void) space;
  166. }
  167.  
  168.  
  169. /*
  170.  * Specialized version gl_clip_interp_all:  just do color.
  171.  */
  172. void gl_clip_interp_color( GLcontext *ctx, GLuint space,
  173.                            GLuint dst, GLfloat t, GLuint in, GLuint out )
  174. {
  175.    struct vertex_buffer *VB = ctx->VB;
  176.    VB->Fcolor[dst][0] = (GLint) LINTERP( t, VB->Fcolor[in][0], VB->Fcolor[out][0] );
  177.    VB->Fcolor[dst][1] = (GLint) LINTERP( t, VB->Fcolor[in][1], VB->Fcolor[out][1] );
  178.    VB->Fcolor[dst][2] = (GLint) LINTERP( t, VB->Fcolor[in][2], VB->Fcolor[out][2] );
  179.    VB->Fcolor[dst][3] = (GLint) LINTERP( t, VB->Fcolor[in][3], VB->Fcolor[out][3] );
  180.    (void) space;
  181. }
  182.  
  183.  
  184.  
  185.  
  186. void gl_ClipPlane( GLcontext* ctx, GLenum plane, const GLfloat *equation )
  187. {
  188.    GLint p;
  189.  
  190.    p = (GLint) plane - (GLint) GL_CLIP_PLANE0;
  191.    if (p<0 || p>=MAX_CLIP_PLANES) {
  192.       gl_error( ctx, GL_INVALID_ENUM, "glClipPlane" );
  193.       return;
  194.    }
  195.  
  196.    /*
  197.     * The equation is transformed by the transpose of the inverse of the
  198.     * current modelview matrix and stored in the resulting eye coordinates.
  199.     */
  200.    if (ctx->NewModelViewMatrix) {
  201.       gl_analyze_modelview_matrix(ctx);
  202.    }
  203.    gl_transform_vector( ctx->Transform.ClipEquation[p], equation,
  204.                 ctx->ModelViewInv );
  205. }
  206.  
  207.  
  208.  
  209. void gl_GetClipPlane( GLcontext* ctx, GLenum plane, GLdouble *equation )
  210. {
  211.    GLint p;
  212.  
  213.    if (INSIDE_BEGIN_END(ctx)) {
  214.       gl_error( ctx, GL_INVALID_OPERATION, "glGetClipPlane" );
  215.       return;
  216.    }
  217.  
  218.    p = (GLint) (plane - GL_CLIP_PLANE0);
  219.    if (p<0 || p>=MAX_CLIP_PLANES) {
  220.       gl_error( ctx, GL_INVALID_ENUM, "glGetClipPlane" );
  221.       return;
  222.    }
  223.  
  224.    equation[0] = (GLdouble) ctx->Transform.ClipEquation[p][0];
  225.    equation[1] = (GLdouble) ctx->Transform.ClipEquation[p][1];
  226.    equation[2] = (GLdouble) ctx->Transform.ClipEquation[p][2];
  227.    equation[3] = (GLdouble) ctx->Transform.ClipEquation[p][3];
  228. }
  229.  
  230.  
  231.  
  232.  
  233. /**********************************************************************/
  234. /*                         View volume clipping.                      */
  235. /**********************************************************************/
  236.  
  237.  
  238. /*
  239.  * Clip a point against the view volume.
  240.  * Input:  v - vertex-vector describing the point to clip
  241.  * Return:  0 = outside view volume
  242.  *          1 = inside view volume
  243.  */
  244. GLuint gl_viewclip_point( const GLfloat v[] )
  245. {
  246.    if (   v[0] > v[3] || v[0] < -v[3]
  247.        || v[1] > v[3] || v[1] < -v[3]
  248.        || v[2] > v[3] || v[2] < -v[3] ) {
  249.       return 0;
  250.    }
  251.    else {
  252.       return 1;
  253.    }
  254. }
  255.  
  256.  
  257.  
  258.  
  259. /*
  260.  * Clip a line segment against the view volume defined by -w<=x,y,z<=w.
  261.  * Input:  i, j - indexes into VB->V* of endpoints of the line
  262.  * Return:  0 = line completely outside of view
  263.  *          1 = line is inside view.
  264.  */
  265. GLuint gl_viewclip_line( GLcontext* ctx, GLuint *i, GLuint *j )
  266. {
  267.    struct vertex_buffer* VB = ctx->VB;
  268.    GLfloat (*coord)[4] = VB->Clip;
  269.  
  270.    GLfloat t, dx, dy, dz, dw;
  271.    register GLuint ii, jj;
  272.  
  273.    ii = *i;
  274.    jj = *j;
  275.  
  276. /*
  277.  * We use 6 instances of this code to clip agains the 6 planes.
  278.  * For each plane, we define the OUTSIDE and COMPUTE_INTERSECTION
  279.  * macros apprpriately.
  280.  */
  281. #define GENERAL_CLIP                            \
  282.    if (OUTSIDE(ii)) {                                           \
  283.       if (OUTSIDE(jj)) {                                        \
  284.          /* both verts are outside ==> return 0 */            \
  285.          return 0;                                              \
  286.       }                                                         \
  287.       else {                                                    \
  288.          /* ii is outside, jj is inside ==> clip */             \
  289.      /* new vertex put in position VB->Free */            \
  290.          COMPUTE_INTERSECTION( VB->Free, jj, ii )                     \
  291.      if (ctx->ClipMask)                        \
  292.             (*ctx->ClipInterpFunc)( ctx, CLIP_SPACE, VB->Free, t, jj, ii );\
  293.      ii = VB->Free;                            \
  294.      VB->Free++;                            \
  295.      if (VB->Free==VB_SIZE)  VB->Free = 1;                \
  296.       }                                                         \
  297.    }                                                            \
  298.    else {                                                       \
  299.       if (OUTSIDE(jj)) {                                        \
  300.          /* ii is inside, jj is outside ==> clip */             \
  301.      /* new vertex put in position VB->Free */            \
  302.          COMPUTE_INTERSECTION( VB->Free, ii, jj );                    \
  303.      if (ctx->ClipMask)                        \
  304.         (*ctx->ClipInterpFunc)( ctx, CLIP_SPACE, VB->Free, t, ii, jj );\
  305.      jj = VB->Free;                            \
  306.      VB->Free++;                            \
  307.      if (VB->Free==VB_SIZE)  VB->Free = 1;                \
  308.       }                                                         \
  309.       /* else both verts are inside ==> do nothing */           \
  310.    }
  311.  
  312.  
  313. #define X(I)    coord[I][0]
  314. #define Y(I)    coord[I][1]
  315. #define Z(I)    coord[I][2]
  316. #define W(I)    coord[I][3]
  317.  
  318. /*
  319.  * Begin clipping
  320.  */
  321.  
  322.    /*** Clip against +X side ***/
  323. #define OUTSIDE(K)      (X(K) > W(K))
  324. #define COMPUTE_INTERSECTION( new, in, out )        \
  325.     dx = X(out) - X(in);                \
  326.     dw = W(out) - W(in);                \
  327.     t = (X(in) - W(in)) / (dw-dx);            \
  328.     X(new) = X(in) + t * dx;            \
  329.     Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  330.     Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  331.     W(new) = W(in) + t * dw;
  332.  
  333.    GENERAL_CLIP
  334.  
  335. #undef OUTSIDE
  336. #undef COMPUTE_INTERSECTION
  337.  
  338.  
  339.    /*** Clip against -X side ***/
  340. #define OUTSIDE(K)      (X(K) < -W(K))
  341. #define COMPUTE_INTERSECTION( new, in, out )        \
  342.     dx = X(out) - X(in);                \
  343.     dw = W(out) - W(in);                \
  344.         t = -(X(in) + W(in)) / (dw+dx);            \
  345.     X(new) = X(in) + t * dx;            \
  346.     Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  347.     Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  348.     W(new) = W(in) + t * dw;
  349.  
  350.    GENERAL_CLIP
  351.  
  352. #undef OUTSIDE
  353. #undef COMPUTE_INTERSECTION
  354.  
  355.  
  356.    /*** Clip against +Y side ***/
  357. #define OUTSIDE(K)      (Y(K) > W(K))
  358. #define COMPUTE_INTERSECTION( new, in, out )        \
  359.     dy = Y(out) - Y(in);                \
  360.     dw = W(out) - W(in);                \
  361.         t = (Y(in) - W(in)) / (dw-dy);            \
  362.     X(new) = X(in) + t * (X(out) - X(in));        \
  363.     Y(new) = Y(in) + t * dy;            \
  364.     Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  365.     W(new) = W(in) + t * dw;
  366.  
  367.    GENERAL_CLIP
  368.  
  369. #undef OUTSIDE
  370. #undef COMPUTE_INTERSECTION
  371.  
  372.  
  373.    /*** Clip against -Y side ***/
  374. #define OUTSIDE(K)      (Y(K) < -W(K))
  375. #define COMPUTE_INTERSECTION( new, in, out )        \
  376.         dy = Y(out) - Y(in);                \
  377.         dw = W(out) - W(in);                \
  378.         t = -(Y(in) + W(in)) / (dw+dy);            \
  379.         X(new) = X(in) + t * (X(out) - X(in));        \
  380.     Y(new) = Y(in) + t * dy;            \
  381.     Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  382.     W(new) = W(in) + t * dw;
  383.  
  384.    GENERAL_CLIP
  385.  
  386. #undef OUTSIDE
  387. #undef COMPUTE_INTERSECTION
  388.  
  389.  
  390.    /*** Clip against +Z side ***/
  391. #define OUTSIDE(K)      (Z(K) > W(K))
  392. #define COMPUTE_INTERSECTION( new, in, out )        \
  393.         dz = Z(out) - Z(in);                \
  394.         dw = W(out) - W(in);                \
  395.         t = (Z(in) - W(in)) / (dw-dz);            \
  396.         X(new) = X(in) + t * (X(out) - X(in));        \
  397.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  398.     Z(new) = Z(in) + t * dz;            \
  399.     W(new) = W(in) + t * dw;
  400.  
  401.    GENERAL_CLIP
  402.  
  403. #undef OUTSIDE
  404. #undef COMPUTE_INTERSECTION
  405.  
  406.  
  407.    /*** Clip against -Z side ***/
  408. #define OUTSIDE(K)      (Z(K) < -W(K))
  409. #define COMPUTE_INTERSECTION( new, in, out )        \
  410.         dz = Z(out) - Z(in);                \
  411.         dw = W(out) - W(in);                \
  412.         t = -(Z(in) + W(in)) / (dw+dz);            \
  413.         X(new) = X(in) + t * (X(out) - X(in));        \
  414.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  415.     Z(new) = Z(in) + t * dz;            \
  416.     W(new) = W(in) + t * dw;
  417.  
  418.    GENERAL_CLIP
  419.  
  420. #undef OUTSIDE
  421. #undef COMPUTE_INTERSECTION
  422.  
  423. #undef GENERAL_CLIP
  424.  
  425.    *i = ii;
  426.    *j = jj;
  427.    return 1;
  428. }
  429.  
  430.  
  431.  
  432.  
  433. /*
  434.  * Clip a polygon against the view volume defined by -w<=x,y,z<=w.
  435.  * Input:  n - number of vertices in input polygon.
  436.  *         vlist - list of indexes into VB->V* of polygon to clip.
  437.  * Output:  vlist - modified list of vertex indexes
  438.  * Return:  number of vertices in resulting polygon
  439.  */
  440. GLuint gl_viewclip_polygon( GLcontext* ctx, GLuint n, GLuint vlist[] )
  441.  
  442. {
  443.    struct vertex_buffer* VB = ctx->VB;
  444.    GLfloat (*coord)[4] = VB->Clip;
  445.  
  446.    GLuint previ, prevj;
  447.    GLuint curri, currj;
  448.    GLuint vlist2[VB_SIZE];
  449.    GLuint n2;
  450.    GLdouble dx, dy, dz, dw, t, neww;
  451.  
  452. /*
  453.  * We use 6 instances of this code to implement clipping against the
  454.  * 6 sides of the view volume.  Prior to each we define the macros:
  455.  *    INLIST = array which lists input vertices
  456.  *    OUTLIST = array which lists output vertices
  457.  *    INCOUNT = variable which is the number of vertices in INLIST[]
  458.  *    OUTCOUNT = variable which is the number of vertices in OUTLIST[]
  459.  *    INSIDE(i) = test if vertex v[i] is inside the view volume
  460.  *    COMPUTE_INTERSECTION(in,out,new) = compute intersection of line
  461.  *              from v[in] to v[out] with the clipping plane and store
  462.  *              the result in v[new]
  463.  */
  464.  
  465. #define GENERAL_CLIP                                                    \
  466.    if (INCOUNT<3)  return 0;                        \
  467.    previ = INCOUNT-1;        /* let previous = last vertex */    \
  468.    prevj = INLIST[previ];                        \
  469.    OUTCOUNT = 0;                                                        \
  470.    for (curri=0;curri<INCOUNT;curri++) {                \
  471.       currj = INLIST[curri];                        \
  472.       if (INSIDE(currj)) {                        \
  473.          if (INSIDE(prevj)) {                        \
  474.             /* both verts are inside ==> copy current to outlist */     \
  475.         OUTLIST[OUTCOUNT] = currj;                    \
  476.         OUTCOUNT++;                            \
  477.          }                                                              \
  478.          else {                                                         \
  479.             /* current is inside and previous is outside ==> clip */    \
  480.         COMPUTE_INTERSECTION( currj, prevj,    VB->Free )        \
  481.         /* if new point not coincident with previous point... */    \
  482.         if (t>0.0) {                        \
  483.            /* interpolate aux info using the value of t */        \
  484.            if (ctx->ClipMask)                    \
  485.           (*ctx->ClipInterpFunc)( ctx, CLIP_SPACE, VB->Free, t, currj, prevj ); \
  486.            VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];        \
  487.            /* output new point */                    \
  488.            OUTLIST[OUTCOUNT] = VB->Free;                \
  489.            VB->Free++;                        \
  490.            if (VB->Free==VB_SIZE)   VB->Free = 1;            \
  491.            OUTCOUNT++;                        \
  492.         }                                \
  493.         /* Output current */                    \
  494.         OUTLIST[OUTCOUNT] = currj;                    \
  495.         OUTCOUNT++;                            \
  496.          }                                                              \
  497.       }                                                                 \
  498.       else {                                                            \
  499.          if (INSIDE(prevj)) {                        \
  500.             /* current is outside and previous is inside ==> clip */    \
  501.         COMPUTE_INTERSECTION( prevj, currj, VB->Free )        \
  502.         /* if new point not coincident with previous point... */    \
  503.         if (t>0.0) {                        \
  504.            /* interpolate aux info using the value of t */        \
  505.            if (ctx->ClipMask)                    \
  506.           (*ctx->ClipInterpFunc)( ctx, CLIP_SPACE, VB->Free, t, prevj, currj ); \
  507.            VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];        \
  508.            /* output new point */                    \
  509.            OUTLIST[OUTCOUNT] = VB->Free;                \
  510.            VB->Free++;                        \
  511.            if (VB->Free==VB_SIZE)   VB->Free = 1;            \
  512.            OUTCOUNT++;                        \
  513.         }                                \
  514.          }                                \
  515.          /* else both verts are outside ==> do nothing */        \
  516.       }                                    \
  517.       /* let previous = current */                    \
  518.       previ = curri;                            \
  519.       prevj = currj;                            \
  520.       /* check for overflowing vertex buffer */                \
  521.       if (OUTCOUNT>=VB_SIZE-1) {                    \
  522.      /* Too many vertices */                    \
  523.          if (OUTLIST==vlist2) {                        \
  524.         /* copy OUTLIST[] to vlist[] */                \
  525.         int i;                            \
  526.         for (i=0;i<VB_SIZE;i++) {                    \
  527.            vlist[i] = OUTLIST[i];                    \
  528.         }                                \
  529.      }                                \
  530.      return VB_SIZE-1;                        \
  531.       }                                    \
  532.    }
  533.  
  534.  
  535. #define X(I)    coord[I][0]
  536. #define Y(I)    coord[I][1]
  537. #define Z(I)    coord[I][2]
  538. #define W(I)    coord[I][3]
  539.  
  540. /*
  541.  * Clip against +X
  542.  */
  543. #define INCOUNT n
  544. #define OUTCOUNT n2
  545. #define INLIST vlist
  546. #define OUTLIST vlist2
  547. #define INSIDE(K)      (X(K) <= W(K))
  548.  
  549. #define COMPUTE_INTERSECTION( in, out, new )        \
  550.         dx = X(out) - X(in);                \
  551.         dw = W(out) - W(in);                \
  552.         t = (X(in)-W(in)) / (dw-dx);            \
  553.     neww = W(in) + t * dw;                \
  554.     X(new) = neww;                    \
  555.     Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  556.     Z(new) = Z(in) + t * (Z(out) - Z(in));         \
  557.     W(new) = neww;
  558.  
  559.    GENERAL_CLIP
  560.  
  561. #undef INCOUNT
  562. #undef OUTCOUNT
  563. #undef INLIST
  564. #undef OUTLIST
  565. #undef INSIDE
  566. #undef COMPUTE_INTERSECTION
  567.  
  568.  
  569. /*
  570.  * Clip against -X
  571.  */
  572. #define INCOUNT n2
  573. #define OUTCOUNT n
  574. #define INLIST vlist2
  575. #define OUTLIST vlist
  576. #define INSIDE(K)       (X(K) >= -W(K))
  577. #define COMPUTE_INTERSECTION( in, out, new )        \
  578.         dx = X(out)-X(in);                          \
  579.         dw = W(out)-W(in);                          \
  580.         t = -(X(in)+W(in)) / (dw+dx);               \
  581.     neww = W(in) + t * dw;                \
  582.         X(new) = -neww;                    \
  583.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  584.         Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  585.         W(new) = neww;
  586.  
  587.    GENERAL_CLIP
  588.  
  589. #undef INCOUNT
  590. #undef OUTCOUNT
  591. #undef INLIST
  592. #undef OUTLIST
  593. #undef INSIDE
  594. #undef COMPUTE_INTERSECTION
  595.  
  596.  
  597. /*
  598.  * Clip against +Y
  599.  */
  600. #define INCOUNT n
  601. #define OUTCOUNT n2
  602. #define INLIST vlist
  603. #define OUTLIST vlist2
  604. #define INSIDE(K)       (Y(K) <= W(K))
  605. #define COMPUTE_INTERSECTION( in, out, new )        \
  606.         dy = Y(out)-Y(in);                          \
  607.         dw = W(out)-W(in);                          \
  608.         t = (Y(in)-W(in)) / (dw-dy);                \
  609.     neww = W(in) + t * dw;                 \
  610.         X(new) = X(in) + t * (X(out) - X(in));        \
  611.         Y(new) = neww;                    \
  612.         Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  613.         W(new) = neww;
  614.  
  615.    GENERAL_CLIP
  616.  
  617. #undef INCOUNT
  618. #undef OUTCOUNT
  619. #undef INLIST
  620. #undef OUTLIST
  621. #undef INSIDE
  622. #undef COMPUTE_INTERSECTION
  623.  
  624.  
  625. /*
  626.  * Clip against -Y
  627.  */
  628. #define INCOUNT n2
  629. #define OUTCOUNT n
  630. #define INLIST vlist2
  631. #define OUTLIST vlist
  632. #define INSIDE(K)       (Y(K) >= -W(K))
  633. #define COMPUTE_INTERSECTION( in, out, new )        \
  634.         dy = Y(out)-Y(in);                          \
  635.         dw = W(out)-W(in);                          \
  636.         t = -(Y(in)+W(in)) / (dw+dy);               \
  637.     neww = W(in) + t * dw;                \
  638.         X(new) = X(in) + t * (X(out) - X(in));        \
  639.         Y(new) = -neww;                    \
  640.         Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  641.         W(new) = neww;
  642.  
  643.    GENERAL_CLIP
  644.  
  645. #undef INCOUNT
  646. #undef OUTCOUNT
  647. #undef INLIST
  648. #undef OUTLIST
  649. #undef INSIDE
  650. #undef COMPUTE_INTERSECTION
  651.  
  652.  
  653.  
  654. /*
  655.  * Clip against +Z
  656.  */
  657. #define INCOUNT n
  658. #define OUTCOUNT n2
  659. #define INLIST vlist
  660. #define OUTLIST vlist2
  661. #define INSIDE(K)       (Z(K) <= W(K))
  662. #define COMPUTE_INTERSECTION( in, out, new )        \
  663.         dz = Z(out)-Z(in);                          \
  664.         dw = W(out)-W(in);                          \
  665.         t = (Z(in)-W(in)) / (dw-dz);                \
  666.     neww = W(in) + t * dw;                \
  667.         X(new) = X(in) + t * (X(out) - X(in));        \
  668.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  669.         Z(new) = neww;                    \
  670.         W(new) = neww;
  671.  
  672.    GENERAL_CLIP
  673.  
  674. #undef INCOUNT
  675. #undef OUTCOUNT
  676. #undef INLIST
  677. #undef OUTLIST
  678. #undef INSIDE
  679. #undef COMPUTE_INTERSECTION
  680.  
  681.  
  682. /*
  683.  * Clip against -Z
  684.  */
  685. #define INCOUNT n2
  686. #define OUTCOUNT n
  687. #define INLIST vlist2
  688. #define OUTLIST vlist
  689. #define INSIDE(K)       (Z(K) >= -W(K))
  690. #define COMPUTE_INTERSECTION( in, out, new )        \
  691.         dz = Z(out)-Z(in);                          \
  692.         dw = W(out)-W(in);                          \
  693.         t = -(Z(in)+W(in)) / (dw+dz);               \
  694.     neww = W(in) + t * dw;                \
  695.         X(new) = X(in) + t * (X(out) - X(in));        \
  696.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  697.         Z(new) = -neww;                    \
  698.         W(new) = neww;
  699.  
  700.    GENERAL_CLIP
  701.  
  702. #undef INCOUNT
  703. #undef INLIST
  704. #undef OUTLIST
  705. #undef INSIDE
  706. #undef COMPUTE_INTERSECTION
  707.  
  708.    /* 'OUTCOUNT' clipped vertices are now back in v[] */
  709.    return OUTCOUNT;
  710.  
  711. #undef GENERAL_CLIP
  712. #undef OUTCOUNT
  713. }
  714.  
  715.  
  716.  
  717.  
  718. /**********************************************************************/
  719. /*         Clipping against user-defined clipping planes.             */
  720. /**********************************************************************/
  721.  
  722.  
  723.  
  724. /*
  725.  * If the dot product of the eye coordinates of a vertex with the
  726.  * stored plane equation components is positive or zero, the vertex
  727.  * is in with respect to that clipping plane, otherwise it is out.
  728.  */
  729.  
  730.  
  731.  
  732. /*
  733.  * Clip a point against the user clipping planes.
  734.  * Input:  v - vertex-vector describing the point to clip.
  735.  * Return:  0 = point was clipped
  736.  *          1 = point not clipped
  737.  */
  738. GLuint gl_userclip_point( GLcontext* ctx, const GLfloat v[] )
  739. {
  740.    GLuint p;
  741.  
  742.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  743.       if (ctx->Transform.ClipEnabled[p]) {
  744.      GLfloat dot = v[0] * ctx->Transform.ClipEquation[p][0]
  745.              + v[1] * ctx->Transform.ClipEquation[p][1]
  746.              + v[2] * ctx->Transform.ClipEquation[p][2]
  747.              + v[3] * ctx->Transform.ClipEquation[p][3];
  748.          if (dot < 0.0F) {
  749.             return 0;
  750.          }
  751.       }
  752.    }
  753.  
  754.    return 1;
  755. }
  756.  
  757.  
  758. #define MAGIC_NUMBER -0.8e-03F
  759.  
  760.  
  761. /* Test if VB->Eye[J] is inside the clipping plane defined by A,B,C,D */
  762. #define INSIDE( J, A, B, C, D )                   \
  763.    ( (VB->Eye[J][0] * A + VB->Eye[J][1] * B            \
  764.     + VB->Eye[J][2] * C + VB->Eye[J][3] * D) >= MAGIC_NUMBER )
  765.  
  766.  
  767. /* Test if VB->Eye[J] is outside the clipping plane defined by A,B,C,D */
  768. #define OUTSIDE( J, A, B, C, D )                   \
  769.    ( (VB->Eye[J][0] * A + VB->Eye[J][1] * B            \
  770.     + VB->Eye[J][2] * C + VB->Eye[J][3] * D) < MAGIC_NUMBER )
  771.  
  772.  
  773. /*
  774.  * Clip a line against the user clipping planes.
  775.  * Input:  i, j - indexes into VB->V*[] of endpoints
  776.  * Output:  i, j - indexes into VB->V*[] of (possibly clipped) endpoints
  777.  * Return:  0 = line completely clipped
  778.  *          1 = line is visible
  779.  */
  780. GLuint gl_userclip_line( GLcontext* ctx, GLuint *i, GLuint *j )
  781. {
  782.    struct vertex_buffer* VB = ctx->VB;
  783.  
  784.    GLuint p, ii, jj;
  785.  
  786.    ii = *i;
  787.    jj = *j;
  788.  
  789.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  790.       if (ctx->Transform.ClipEnabled[p]) {
  791.      register GLfloat a, b, c, d;
  792.      a = ctx->Transform.ClipEquation[p][0];
  793.      b = ctx->Transform.ClipEquation[p][1];
  794.      c = ctx->Transform.ClipEquation[p][2];
  795.      d = ctx->Transform.ClipEquation[p][3];
  796.  
  797.          if (OUTSIDE( ii, a,b,c,d  )) {
  798.             if (OUTSIDE( jj, a,b,c,d )) {
  799.                /* ii and jj outside ==> quit */
  800.                return 0;
  801.             }
  802.             else {
  803.                /* ii is outside, jj is inside ==> clip */
  804.                GLfloat dx, dy, dz, dw, t, denom;
  805.                dx = VB->Eye[ii][0] - VB->Eye[jj][0];
  806.                dy = VB->Eye[ii][1] - VB->Eye[jj][1];
  807.                dz = VB->Eye[ii][2] - VB->Eye[jj][2];
  808.                dw = VB->Eye[ii][3] - VB->Eye[jj][3];
  809.            denom = dx*a + dy*b + dz*c + dw*d;
  810.            if (denom==0.0) {
  811.           t = 0.0;
  812.            }
  813.            else {
  814.           t = -(VB->Eye[jj][0]*a+VB->Eye[jj][1]*b
  815.                +VB->Eye[jj][2]*c+VB->Eye[jj][3]*d) / denom;
  816.                   if (t>1.0F)  t = 1.0F;
  817.            }
  818.            VB->Eye[VB->Free][0] = VB->Eye[jj][0] + t * dx;
  819.            VB->Eye[VB->Free][1] = VB->Eye[jj][1] + t * dy;
  820.            VB->Eye[VB->Free][2] = VB->Eye[jj][2] + t * dz;
  821.            VB->Eye[VB->Free][3] = VB->Eye[jj][3] + t * dw;
  822.  
  823.            /* Interpolate colors, indexes, and/or texture coords */
  824.            if (ctx->ClipMask)
  825.           (*ctx->ClipInterpFunc)( ctx, EYE_SPACE, VB->Free, t, jj, ii );
  826.  
  827.            ii = VB->Free;
  828.            VB->Free++;
  829.            if (VB->Free==VB_SIZE)   VB->Free = 1;
  830.             }
  831.          }
  832.          else {
  833.             if (OUTSIDE( jj, a,b,c,d )) {
  834.                /* ii is inside, jj is outside ==> clip */
  835.                GLfloat dx, dy, dz, dw, t, denom;
  836.                dx = VB->Eye[jj][0] - VB->Eye[ii][0];
  837.                dy = VB->Eye[jj][1] - VB->Eye[ii][1];
  838.                dz = VB->Eye[jj][2] - VB->Eye[ii][2];
  839.                dw = VB->Eye[jj][3] - VB->Eye[ii][3];
  840.            denom = dx*a + dy*b + dz*c + dw*d;
  841.            if (denom==0.0) {
  842.           t = 0.0;
  843.            }
  844.            else {
  845.           t = -(VB->Eye[ii][0]*a+VB->Eye[ii][1]*b
  846.                +VB->Eye[ii][2]*c+VB->Eye[ii][3]*d) / denom;
  847.                   if (t>1.0F)  t = 1.0F;
  848.            }
  849.            VB->Eye[VB->Free][0] = VB->Eye[ii][0] + t * dx;
  850.            VB->Eye[VB->Free][1] = VB->Eye[ii][1] + t * dy;
  851.            VB->Eye[VB->Free][2] = VB->Eye[ii][2] + t * dz;
  852.            VB->Eye[VB->Free][3] = VB->Eye[ii][3] + t * dw;
  853.  
  854.            /* Interpolate colors, indexes, and/or texture coords */
  855.            if (ctx->ClipMask)
  856.           (*ctx->ClipInterpFunc)( ctx, EYE_SPACE, VB->Free, t, ii, jj );
  857.  
  858.            jj = VB->Free;
  859.            VB->Free++;
  860.            if (VB->Free==VB_SIZE)   VB->Free = 1;
  861.             }
  862.             else {
  863.                /* ii and jj inside ==> do nothing */
  864.             }
  865.          }
  866.       }
  867.    }
  868.  
  869.    *i = ii;
  870.    *j = jj;
  871.    return 1;
  872. }
  873.  
  874.  
  875.  
  876.  
  877. /*
  878.  * Clip a polygon against the user clipping planes defined in eye coordinates.
  879.  * Input:  n - number of vertices.
  880.  *         vlist - list of vertices in input polygon.
  881.  * Output:  vlist - list of vertices in output polygon.
  882.  * Return:  number of vertices after clipping.
  883.  */
  884. GLuint gl_userclip_polygon( GLcontext* ctx, GLuint n, GLuint vlist[] )
  885. {
  886.    struct vertex_buffer* VB = ctx->VB;
  887.  
  888.    GLuint vlist2[VB_SIZE];
  889.    GLuint *inlist, *outlist;
  890.    GLuint incount, outcount;
  891.    GLuint curri, currj;
  892.    GLuint previ, prevj;
  893.    GLuint p;
  894.  
  895.    /* initialize input vertex list */
  896.    incount = n;
  897.    inlist = vlist;
  898.    outlist = vlist2;
  899.  
  900.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  901.       if (ctx->Transform.ClipEnabled[p]) {
  902.      register float a = ctx->Transform.ClipEquation[p][0];
  903.      register float b = ctx->Transform.ClipEquation[p][1];
  904.      register float c = ctx->Transform.ClipEquation[p][2];
  905.      register float d = ctx->Transform.ClipEquation[p][3];
  906.  
  907.      if (incount<3)  return 0;
  908.  
  909.      /* initialize prev to be last in the input list */
  910.      previ = incount - 1;
  911.      prevj = inlist[previ];
  912.  
  913.          outcount = 0;
  914.  
  915.          for (curri=0;curri<incount;curri++) {
  916.         currj = inlist[curri];
  917.  
  918.             if (INSIDE(currj, a,b,c,d)) {
  919.                if (INSIDE(prevj, a,b,c,d)) {
  920.                   /* both verts are inside ==> copy current to outlist */
  921.           outlist[outcount++] = currj;
  922.                }
  923.                else {
  924.                   /* current is inside and previous is outside ==> clip */
  925.                   GLfloat dx, dy, dz, dw, t, denom;
  926.           /* compute t */
  927.           dx = VB->Eye[prevj][0] - VB->Eye[currj][0];
  928.           dy = VB->Eye[prevj][1] - VB->Eye[currj][1];
  929.           dz = VB->Eye[prevj][2] - VB->Eye[currj][2];
  930.           dw = VB->Eye[prevj][3] - VB->Eye[currj][3];
  931.           denom = dx*a + dy*b + dz*c + dw*d;
  932.           if (denom==0.0) {
  933.              t = 0.0;
  934.           }
  935.           else {
  936.              t = -(VB->Eye[currj][0]*a+VB->Eye[currj][1]*b
  937.                +VB->Eye[currj][2]*c+VB->Eye[currj][3]*d) / denom;
  938.                      if (t>1.0F) {
  939.                         t = 1.0F;
  940.                      }
  941.           }
  942.           /* interpolate new vertex position */
  943.           VB->Eye[VB->Free][0] = VB->Eye[currj][0] + t*dx;
  944.           VB->Eye[VB->Free][1] = VB->Eye[currj][1] + t*dy;
  945.           VB->Eye[VB->Free][2] = VB->Eye[currj][2] + t*dz;
  946.           VB->Eye[VB->Free][3] = VB->Eye[currj][3] + t*dw;
  947.  
  948.           /* interpolate color, index, and/or texture coord */
  949.           if (ctx->ClipMask) {
  950.              (*ctx->ClipInterpFunc)( ctx, EYE_SPACE, VB->Free, t, currj, prevj);
  951.           }
  952.           VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];
  953.  
  954.           /* output new vertex */
  955.           outlist[outcount++] = VB->Free;
  956.           VB->Free++;
  957.           if (VB->Free==VB_SIZE)   VB->Free = 1;
  958.           /* output current vertex */
  959.           outlist[outcount++] = currj;
  960.                }
  961.             }
  962.             else {
  963.                if (INSIDE(prevj, a,b,c,d)) {
  964.                   /* current is outside and previous is inside ==> clip */
  965.                   GLfloat dx, dy, dz, dw, t, denom;
  966.           /* compute t */
  967.                   dx = VB->Eye[currj][0]-VB->Eye[prevj][0];
  968.                   dy = VB->Eye[currj][1]-VB->Eye[prevj][1];
  969.                   dz = VB->Eye[currj][2]-VB->Eye[prevj][2];
  970.                   dw = VB->Eye[currj][3]-VB->Eye[prevj][3];
  971.           denom = dx*a + dy*b + dz*c + dw*d;
  972.           if (denom==0.0) {
  973.              t = 0.0;
  974.           }
  975.           else {
  976.              t = -(VB->Eye[prevj][0]*a+VB->Eye[prevj][1]*b
  977.                +VB->Eye[prevj][2]*c+VB->Eye[prevj][3]*d) / denom;
  978.                      if (t>1.0F) {
  979.                         t = 1.0F;
  980.                      }
  981.           }
  982.           /* interpolate new vertex position */
  983.           VB->Eye[VB->Free][0] = VB->Eye[prevj][0] + t*dx;
  984.           VB->Eye[VB->Free][1] = VB->Eye[prevj][1] + t*dy;
  985.           VB->Eye[VB->Free][2] = VB->Eye[prevj][2] + t*dz;
  986.           VB->Eye[VB->Free][3] = VB->Eye[prevj][3] + t*dw;
  987.  
  988.           /* interpolate color, index, and/or texture coord */
  989.           if (ctx->ClipMask) {
  990.              (*ctx->ClipInterpFunc)( ctx, EYE_SPACE, VB->Free, t, prevj, currj);
  991.           }
  992.           VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];
  993.  
  994.           /* output new vertex */
  995.           outlist[outcount++] = VB->Free;
  996.           VB->Free++;
  997.           if (VB->Free==VB_SIZE)   VB->Free = 1;
  998.            }
  999.                /* else  both verts are outside ==> do nothing */
  1000.             }
  1001.  
  1002.         previ = curri;
  1003.         prevj = currj;
  1004.  
  1005.         /* check for overflowing vertex buffer */
  1006.             if (outcount>=VB_SIZE-1) {
  1007.                /* Too many vertices */
  1008.                if (outlist!=vlist2) {
  1009.                   MEMCPY( vlist, vlist2, outcount * sizeof(GLuint) );
  1010.                }
  1011.                return VB_SIZE-1;
  1012.             }
  1013.  
  1014.          }  /* for i */
  1015.  
  1016.          /* swap inlist and outlist pointers */
  1017.          {
  1018.             GLuint *tmp;
  1019.             tmp = inlist;
  1020.             inlist = outlist;
  1021.             outlist = tmp;
  1022.             incount = outcount;
  1023.          }
  1024.  
  1025.       } /* if */
  1026.    } /* for p */
  1027.  
  1028.    /* outlist points to the list of vertices resulting from the last */
  1029.    /* clipping.  If outlist == vlist2 then we have to copy the vertices */
  1030.    /* back to vlist */
  1031.    if (outlist!=vlist2) {
  1032.       MEMCPY( vlist, vlist2, outcount * sizeof(GLuint) );
  1033.    }
  1034.  
  1035.    return outcount;
  1036. }
  1037.  
  1038.